package com.jacklei.tree;

import java.util.*;

//二叉树
public class BinaryTree {
    public static void main(String[] args) {
        initTree();
        postorderTraversal(tree);
        System.out.println();
        postorderTraversalPro(tree);

    }

    public BinaryTree() {
        initTree();
    }

    public static Node<Integer> tree = new Node(1);

    public static void initTree(){


        tree.left = new Node<Integer>(2);
        tree.left.left = new Node<Integer>(4);
        tree.left.right = new Node<Integer>(5);

        tree.right = new Node(3);
        tree.right.left = new Node<Integer>(6);
        tree.right.right = new Node<Integer>(7);
    }

    static class Node <T>{
        public T value;
        public Node right;
        public Node left;

        public Node(T value) {
            this.value = value;
        }
    }

    //二叉树的前序遍历（深度遍历）（递归法）
    public static void preorderTraversal(Node root){
        if(root == null) return;
        System.out.println(root.value);
        preorderTraversal(root.left);
        preorderTraversal(root.right);

    }
    //二叉树的前序遍历（深度遍历）（非递归法）
    public static void preorderTraversalPro(Node root){
        if(root == null) return;
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node pop = stack.pop();
            System.out.println(pop.value);
            if(pop.right != null){
                stack.push(pop.right);
            }
            if(pop.left != null){
                stack.push(pop.left);
            }
        }


    }
    //二叉树的中序遍历（递归法）
    public static void inorderTraversal(Node root){
        if(root == null) return;
        preorderTraversal(root.left);
        System.out.println(root.value);
        preorderTraversal(root.right);

    }
    //二叉树的中序遍历（非递归法）
    public  static void inorderTraversalPro(Node root){
        if(root == null)return;
        Stack<Node> stack = new Stack<>();
        HashSet<Node> set = new HashSet<>();
        stack.add(root);

        while (!stack.isEmpty()){

            Node pop = stack.pop();
            while ((pop.left) != null && !set.contains(pop.left)){
                stack.push(pop);
                stack.push(pop.left);
                pop = pop.left;
            }
            //此时的树的最左孩子在栈顶
            if (set.contains(pop)){
                pop = stack.pop();
            }
            if(!set.contains(pop)){
                System.out.print(pop.value);
                set.add(pop);
            }
            if(pop.right != null){
                stack.push(pop.right);
            }
        }
        System.out.println();
    }
    //二叉树的后序序遍历（递归法）
    public static void postorderTraversal(Node root){
        if(root == null) return;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.value);
    }
    //二叉树的后序序遍历（非递归递归法）
    public static void postorderTraversalPro(Node root){
        if(root == null) return;
        Stack<Node> In = new Stack<>();
        Stack<Node> Out = new Stack<>();
        In.push(root);
        while (!In.isEmpty()){
            Node pop = In.pop();
            Out.push(pop);
            if(pop.left != null)
                In.push(pop.left);
            if (pop.right != null)
                In.push(pop.right);
        }
        while (!Out.isEmpty()){
            Node pop = Out.pop();
            System.out.print(pop.value);
        }

    }
    //二叉树二的宽度遍历
    public static void BreadthTraversal(Node root){
        if(root == null) return;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node poll = queue.poll();
            System.out.print(poll.value);
            if(poll.left != null)
                queue.add(poll.left);
            if(poll.right != null)
                queue.add(poll.right);
        }
        System.out.println();
    }
}
